package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.Unknown;

import java.util.Arrays;

/**
 *
 */
public class LC795_2  implements Unknown {
    /**
     * Example :
     * Input:
     * A = [2, 1, 4, 3]
     * L = 2
     * R = 3
     * Output: 3
     * Explanation: There are three subarrays that meet the requirements: [2], [2, 1], [3].
     * <p>
     * 22243
     * 222143
     * 错误写法
     */
    public int numSubarrayBoundedMax(int[] A, int L, int R) {
        int total = 0;
        int lastBigger = -1, lastMidNum = 0;
        for (int i = 0; i < A.length; i++) {
            if (A[i] > R) {
                lastBigger = i;
                lastMidNum = 0;//tzpdo 关键行
            } else if (A[i] < L) {
                total += lastMidNum;
            } else {
                lastMidNum = i - lastBigger;
                total += i - lastBigger;
            }
        }
        return total;
    }

    public static void main(String[] args) {
        int[] a = new int[]{876, 880, 482, 260, 132, 421, 732, 703, 795, 420, 871, 445, 400, 291, 358, 589, 617, 202, 755, 810, 227, 813, 549, 791, 418, 528, 835, 401, 526, 584, 873, 662, 13, 314, 988, 101, 299, 816, 833, 224, 160, 852, 179, 769, 646, 558, 661, 808, 651, 982, 878, 918, 406, 551, 467, 87, 139, 387, 16, 531, 307, 389, 939, 551, 613, 36, 528, 460, 404, 314, 66, 111, 458, 531, 944, 461, 951, 419, 82, 896, 467, 353, 704, 905, 705, 760, 61, 422, 395, 298, 127, 516, 153, 299, 801, 341, 668, 598, 98, 241};
        System.out.println(new LC795_2().numSubarrayBoundedMax(a, 658, 719));//正确答案19
    }
}
